<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.8.0">
  <meta charset="utf-8">
  

  
  <title>第十三章-红黑树 | 章军的博客</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="红黑树">
<meta name="keywords" content="rb tree">
<meta property="og:type" content="article">
<meta property="og:title" content="第十三章-红黑树">
<meta property="og:url" content="http://octopuscloud.top/2019/06/02/十三章-红黑树/index.html">
<meta property="og:site_name" content="章军的博客">
<meta property="og:description" content="红黑树">
<meta property="og:locale" content="China">
<meta property="og:updated_time" content="2019-09-11T04:27:11.740Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="第十三章-红黑树">
<meta name="twitter:description" content="红黑树">
  
    <link rel="alternate" href="/atom.xml" title="章军的博客" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  <link rel="stylesheet" href="/css/style.css">
</head>
</html>
<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">章军的博客</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="Search"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://octopuscloud.top"></form>
      </div>
    </div>
  </div>
</header>
      <div class="outer">
        <section id="main"><article id="post-十三章-红黑树" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2019/06/02/十三章-红黑树/" class="article-date">
  <time datetime="2019-06-02T06:38:44.000Z" itemprop="datePublished">2019-06-02</time>
</a>
    
  <div class="article-category">
    <a class="article-category-link" href="/categories/ReadNote/">ReadNote</a>
  </div>

  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      第十三章-红黑树
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h1 id="红黑树"><a href="#红黑树" class="headerlink" title="红黑树"></a>红黑树</h1><a id="more"></a>
<h2 id="红黑树的基本属性及性质"><a href="#红黑树的基本属性及性质" class="headerlink" title="红黑树的基本属性及性质"></a>红黑树的基本属性及性质</h2><p>  红黑树是一种二叉查找树 ，但在每个节点上添加了一个存储位来表示颜色 。红黑树树的每个节点包含了 ： color ，key ， right ，left ， p ，data 。如果某个节点没有父亲节点或者子节点 ，这该域指针应该包含值 NIL 。</p>
<p>  一些基本的概念 ：<br>  外节点 ：把 NIL 视为外节点 。<br>  内节点 ：把带关键字的节点视为树的内节点 。<br>  哨兵节点(nil[T]) ： 哨兵节点的颜色为 <strong>BLACK</strong> ，其他域中值为任意值 。我们用 nil[T] (哨兵节点) 。来代替 NIL 。<br>  黑高度 ： 从某个节点 x 出发 ( 不包括该节点 ) 到达一个叶节点的任意一条路径上 ，黑色节点的个数称为黑高度 ，用 bh(x) 表示 。</p>
<p>  一颗红黑树右下面五点属性 ：</p>
<ol>
<li>每个节点都是红色或者黑色的 。</li>
<li>树的根节点都是黑色的 。</li>
<li>每个叶子节点都是黑色的 。(NIL)</li>
<li>如果一个节点是红色的，它的子节点都是黑色的 。</li>
<li>对于每个节点，从该节点到其子孙节点的所有路径上都包含相同数目的黑节点 。</li>
</ol>
<h2 id="旋转"><a href="#旋转" class="headerlink" title="旋转"></a>旋转</h2><p>  在 RB-Tree 的中 ，做插入和删除动作时 ，有时会造成插入和删除后的 RB-Tree 不在符合 RB-Tree 的性质要求 。此时需要通过变色或者旋转来使得经过着色和旋转后的 RB-Tree 符合性质要求 。</p>
<h3 id="左旋转"><a href="#左旋转" class="headerlink" title="左旋转"></a>左旋转</h3>  <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line">   |                                 |</span><br><span class="line">   X                                 Y</span><br><span class="line"> /  \                              /   \</span><br><span class="line">A    Y    == left rotate ===&gt;     X     C</span><br><span class="line">   /   \                        /   \ </span><br><span class="line">  B     C                      A     B</span><br><span class="line"></span><br><span class="line">LEFT-ROTATE(T, x)</span><br><span class="line">  y ← right[x]</span><br><span class="line">  right[x] ← left[y]</span><br><span class="line"></span><br><span class="line">  if left[y] != nil[T]</span><br><span class="line">    p[left[y]] ← x</span><br><span class="line"></span><br><span class="line">  p[y] ← p[x]</span><br><span class="line">  if p[x] == nil[T]</span><br><span class="line">    root[t] ← y</span><br><span class="line">  else if x == left[p[x]]</span><br><span class="line">    left[p[x]] ← y</span><br><span class="line">  else</span><br><span class="line">    right[p[x]] ← y</span><br><span class="line"></span><br><span class="line">  left[y] ← x</span><br><span class="line">  p[x] ← y</span><br></pre></td></tr></table></figure>
<h3 id="右旋转"><a href="#右旋转" class="headerlink" title="右旋转"></a>右旋转</h3>  <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line">      |                                         |      </span><br><span class="line">      Y                                         X      </span><br><span class="line">    /   \                                     /  \     </span><br><span class="line">   X     C    == right rotate ==&gt;            A    Y    </span><br><span class="line"> /   \                                          /   \  </span><br><span class="line">A     B                                        B     C </span><br><span class="line"></span><br><span class="line">RIGHT-ROTATE(T, y)</span><br><span class="line">x ← right[y]</span><br><span class="line"></span><br><span class="line">if rihgt[x] != C </span><br><span class="line">  left[y] ← right[x]</span><br><span class="line"></span><br><span class="line">p[x] = p[y]</span><br><span class="line">if p[y] == nil[T]</span><br><span class="line">  root[T] ← x</span><br><span class="line">else if left[p[x]] == y</span><br><span class="line">  left[p[y]] ← x</span><br><span class="line">else </span><br><span class="line">  right[p[y]] ← x</span><br><span class="line"></span><br><span class="line">right[x] ← y</span><br><span class="line">p[y] ← x</span><br></pre></td></tr></table></figure>
<h2 id="RB-Tree-插入节点"><a href="#RB-Tree-插入节点" class="headerlink" title="RB-Tree 插入节点"></a>RB-Tree 插入节点</h2><p>  在 RB-Tree 插入的过程中 ，我们先把 RB-Tree 当成一颗普通的 SEARCH-Tree 树进行插入节点 z 。然后将节点 z 着色为红色 。为保证红黑树的性质能够保持 ，我们调用一个辅助的程序 RB-INSERT-FIX 来对节点重新着色并旋转来保证红黑树的性质 。</p>
  <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line">RB-Insert(T, z)</span><br><span class="line">y ← nil[T]</span><br><span class="line">x ← root[T]</span><br><span class="line"></span><br><span class="line">while x != nil[T]</span><br><span class="line">  y ← x</span><br><span class="line">  if key[z] &lt; key[x]</span><br><span class="line">    x = left[x]</span><br><span class="line">  else</span><br><span class="line">    x = right[x]</span><br><span class="line">p[z] ← y</span><br><span class="line"></span><br><span class="line">if y == nil[T]</span><br><span class="line">  root[T] ← z</span><br><span class="line">else if key[z] &lt; key[y]</span><br><span class="line">  left[y] ← z</span><br><span class="line">else </span><br><span class="line">  right[y] ← z</span><br><span class="line"></span><br><span class="line">left[z] ← nil[T]</span><br><span class="line">right[z] ← nil[T]</span><br><span class="line">color[z] ← RED</span><br><span class="line">RB-INSERT-FIX(T, z)</span><br></pre></td></tr></table></figure>
<p>  在插入节点 z 的过程中 ，会出现下面的两种情况 ，而此时不能满足 RB-Tree 树的性质要求 ：</p>
<ol>
<li>当 z 作为根节点被插入到 RB-Tree 中 。( 性质2: 树的根节点都是黑色的 。)</li>
<li><p>当 z 节点的父亲节点也为红色 。 ( 性质4: 如果一个节点是红色的，它的子节点都是黑色的 。)</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line">RB-INSERT-FIX(T, z)</span><br><span class="line">  while color[p[z]] == RED</span><br><span class="line"></span><br><span class="line">    if p[z] == left[p[p[z]]]</span><br><span class="line">      y ← right[p[p[z]]]</span><br><span class="line"></span><br><span class="line">      if color[y] == RED</span><br><span class="line">        color[p[z]] ← BLACK </span><br><span class="line">        color[p[p[z]]] ← RED</span><br><span class="line">        color[y] ← BLACK</span><br><span class="line">        z ← p[p[z]]</span><br><span class="line"></span><br><span class="line">      else if z == right[p[z]]</span><br><span class="line">        z ← p[z]</span><br><span class="line">        LEFT-ROTATE(T, z)</span><br><span class="line">      </span><br><span class="line">     color[p[z]] ← BLACK</span><br><span class="line">     color[p[z]] ←  RED</span><br><span class="line">     RIGHT-ROTATE(T, p[p[z]])</span><br><span class="line">  else  </span><br><span class="line">      &lt;!--same as then clause with &quot;right&quot; and &quot;left&quot; exchange--&gt;</span><br><span class="line">      y = left[p[p[z]]]</span><br><span class="line">      if color[y] == RED</span><br><span class="line">        color[p[z]] ← BLACK </span><br><span class="line">        color[p[p[z]]] ← RED</span><br><span class="line">        color[y] ← BLACK</span><br><span class="line">        z ← p[p[z]]</span><br><span class="line"></span><br><span class="line">      else if z == left[p[z]]</span><br><span class="line">        z ← p[z]</span><br><span class="line">        RIGHT-ROTATE(T, z)</span><br><span class="line">    </span><br><span class="line">      color[p[z]] = BLACK</span><br><span class="line">      color[p[p[z]]] = RED</span><br><span class="line">      LEFT-ROTATE(T, p[p[z]])</span><br></pre></td></tr></table></figure>
</li>
<li><p>父亲节点是祖父节点的左子节点</p>
<p>1.1 叔父节点为 RED .<br> 父亲节点染黑色 ，叔父节点染黑色 ，祖父节点染红色 。</p>
<p>1.2 z 节点是父亲节点的右子节点 。<br> 以 z 节点的父亲节点左旋转</p>
<p>1.3 z 节点是父亲节点的左节点　。<br>　将父亲节点染黑 ，祖父节点染红 。以祖父节点作为支点右旋转 。</p>
</li>
<li><p>父亲节点是祖父节点的右子节点<br>2.1 叔父节点为 RED .<br> 父亲节点染黑色 ，叔父节点染黑色 ，祖父节点染红色 。</p>
<p>2.2 z 节点是父亲节点的左子节点 。<br> 以 z 节点的父亲节点右旋转</p>
<p>2.3 z 节点是父亲节点的右节点　。<br>　将父亲节点染黑 ，祖父节点染红 。以祖父节点作为支点左旋转 。</p>
</li>
</ol>
<h2 id="删除节点"><a href="#删除节点" class="headerlink" title="删除节点"></a>删除节点</h2><p>  RB-Tree 删除一个节点类似于 SEARCH-Tree 删除一个节点 ，但在删除了一个节点后 ，剩下的节点组成的树并不能满足 RB-Tree 的要求 。会调用 RB-DELETE-FIX 来使得剩下的节点组成的 RB-Tree 符合红黑树的性质 。</p>
  <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line">RB-Delete(T, z)</span><br><span class="line">  if left[z] == nil or right[z] == nil</span><br><span class="line">    y ← z</span><br><span class="line">  else</span><br><span class="line">    y ← SUCCESSOR-TREE(z)</span><br><span class="line"></span><br><span class="line">  if left[y] != nil[T]</span><br><span class="line">    x ← left[y]</span><br><span class="line">  else</span><br><span class="line">    x ← right[y]</span><br><span class="line"></span><br><span class="line">  p[x] ← p[y]</span><br><span class="line">  if p[y] != nil[T]</span><br><span class="line">    root[T] ← x</span><br><span class="line">  else if y = left[p[y]]</span><br><span class="line">    left[p[y]] ← x</span><br><span class="line">  else </span><br><span class="line">    right[p[y]] ← x</span><br><span class="line"></span><br><span class="line">  if y != z</span><br><span class="line">    key[z] ← key[y]</span><br><span class="line">    copy y to z</span><br><span class="line"></span><br><span class="line">  if color[y] == BLACK</span><br><span class="line">    RB-DELETE-FIX(T, x)</span><br><span class="line"></span><br><span class="line">  return y</span><br></pre></td></tr></table></figure>
<ol>
<li><p>节点 x 是父亲节点的左子节点</p>
<p>1.1 兄弟节点为红色<br>将兄弟节点染黑 ，父亲节点染红 ，以父亲节点为支点做左旋转 。</p>
<p>1.2 兄弟节点的子节点都是黑色 ，兄弟节点为黑色 。<br>将兄弟节点染黑</p>
<p>1.3 兄弟节点只有右子节点为黑色 ，兄弟节点为黑色 。<br>将兄弟节点染红 ，左子节点染黑 ，以兄弟节点作为支点做右旋转</p>
<p>1.4 兄弟节点的右孩子节点是红色 ，兄弟节点为黑色 。<br>兄弟节点染父亲节点颜色 ，父亲节点颜色染黑色 ，兄弟节点右孩子节点染黑色 。以父亲节点作为支点做左旋转 。</p>
</li>
</ol>
<h2 id="code-1"><a href="#code-1" class="headerlink" title="[code][1]"></a>[code][1]</h2><p>1:  <a href="mailto:git@github.com" target="_blank" rel="noopener">git@github.com</a>:singledo/SortCode.git</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://octopuscloud.top/2019/06/02/十三章-红黑树/" data-id="ck471vq1o002132fz984e6ttd" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/rb-tree/">rb tree</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2019/06/09/十五章-动态规划/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Newer</strong>
      <div class="article-nav-title">
        
          十五章-动态规划
        
      </div>
    </a>
  
  
    <a href="/2019/05/24/gdb-基本用法/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title">gdb-基本用法</div>
    </a>
  
</nav>

  
</article>

</section>
        
          <aside id="sidebar">
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Categories</h3>
    <div class="widget">
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/categories/RFC/">RFC</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/RFC-protocol/">RFC protocol</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ReadNote/">ReadNote</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/linux/">linux</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/protocols/">protocols</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/tools/">tools</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tags</h3>
    <div class="widget">
      <ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/C/">C</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Data-Struct/">Data Struct</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Ethernet-II/">Ethernet II</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Frame-Format/">Frame Format</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/I2C/">I2C</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/IPv6/">IPv6</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Neighbour-Discover-Protocol/">Neighbour Discover Protocol</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/RFC/">RFC</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/SNMP/">SNMP</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/arthmetic/">arthmetic</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/cgdb/">cgdb</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/chapter-15/">chapter 15</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/data-struct/">data struct</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/deb/">deb</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/defalt-path-for-so-file/">defalt path for so file</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/editer/">editer</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/file-system/">file system</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/gdb-debug/">gdb debug</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/hash/">hash</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/linux/">linux</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/linux-driver/">linux driver</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/platform-bus/">platform bus</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/pointer-array/">pointer, array</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/pseudocode/">pseudocode</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/rb-tree/">rb tree</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/sort/">sort</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/ssh-key/">ssh key</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/symbol/">symbol</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/tool/">tool</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/tools/">tools</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/图/">图</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/通信协议/">通信协议</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tag Cloud</h3>
    <div class="widget tagcloud">
      <a href="/tags/C/" style="font-size: 10px;">C</a> <a href="/tags/Data-Struct/" style="font-size: 10px;">Data Struct</a> <a href="/tags/Ethernet-II/" style="font-size: 10px;">Ethernet II</a> <a href="/tags/Frame-Format/" style="font-size: 10px;">Frame Format</a> <a href="/tags/I2C/" style="font-size: 10px;">I2C</a> <a href="/tags/IPv6/" style="font-size: 15px;">IPv6</a> <a href="/tags/Neighbour-Discover-Protocol/" style="font-size: 10px;">Neighbour Discover Protocol</a> <a href="/tags/RFC/" style="font-size: 10px;">RFC</a> <a href="/tags/SNMP/" style="font-size: 10px;">SNMP</a> <a href="/tags/arthmetic/" style="font-size: 10px;">arthmetic</a> <a href="/tags/cgdb/" style="font-size: 10px;">cgdb</a> <a href="/tags/chapter-15/" style="font-size: 10px;">chapter 15</a> <a href="/tags/data-struct/" style="font-size: 15px;">data struct</a> <a href="/tags/deb/" style="font-size: 10px;">deb</a> <a href="/tags/defalt-path-for-so-file/" style="font-size: 10px;">defalt path for so file</a> <a href="/tags/editer/" style="font-size: 10px;">editer</a> <a href="/tags/file-system/" style="font-size: 10px;">file system</a> <a href="/tags/gdb-debug/" style="font-size: 10px;">gdb debug</a> <a href="/tags/hash/" style="font-size: 10px;">hash</a> <a href="/tags/linux/" style="font-size: 20px;">linux</a> <a href="/tags/linux-driver/" style="font-size: 10px;">linux driver</a> <a href="/tags/platform-bus/" style="font-size: 10px;">platform bus</a> <a href="/tags/pointer-array/" style="font-size: 10px;">pointer, array</a> <a href="/tags/pseudocode/" style="font-size: 10px;">pseudocode</a> <a href="/tags/rb-tree/" style="font-size: 10px;">rb tree</a> <a href="/tags/sort/" style="font-size: 20px;">sort</a> <a href="/tags/ssh-key/" style="font-size: 10px;">ssh key</a> <a href="/tags/symbol/" style="font-size: 10px;">symbol</a> <a href="/tags/tool/" style="font-size: 10px;">tool</a> <a href="/tags/tools/" style="font-size: 10px;">tools</a> <a href="/tags/图/" style="font-size: 10px;">图</a> <a href="/tags/通信协议/" style="font-size: 10px;">通信协议</a>
    </div>
  </div>

  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/12/">December 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/11/">November 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/10/">October 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/09/">September 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/08/">August 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/07/">July 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/06/">June 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/05/">May 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/04/">April 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/03/">March 2019</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2019/12/15/TMUX-使用/">TMUX-使用</a>
          </li>
        
          <li>
            <a href="/2019/11/02/linux-platform-bus-总线分析/platform/">(no title)</a>
          </li>
        
          <li>
            <a href="/2019/11/02/十二章-二叉搜索树/">算法导论-第十二章 二叉查找树</a>
          </li>
        
          <li>
            <a href="/2019/11/02/SegmentationFault-Debug/">(no title)</a>
          </li>
        
          <li>
            <a href="/2019/10/19/linux-platform-bus-总线分析/">linux platform bus 总线分析</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2019 zhangjun<br>
      Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>
    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    

<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>


  <link rel="stylesheet" href="/fancybox/jquery.fancybox.css">
  <script src="/fancybox/jquery.fancybox.pack.js"></script>


<script src="/js/script.js"></script>



  </div>
</body>
</html>